package com.code.leetcode._202507;

//53 最大子数组和
public class MaxSubArray {
    /**
     * 给你一个整数数组nums，请你找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
     * 子数组是数组中的一个联系部分。
     * 示例1：输入：num=[-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组[4,-1,2,1]的和最大为6
     * 示例2：输入：nums=[1]
     * 输出：1
     * 示例3：输入：nums=[5,4,-1,7,8]
     * 输出：23
     **/
    public static void main(String[] args) {
        MaxSubArray m = new MaxSubArray();
        System.out.println(m.maxSubArray1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    /**
     * 动态规划
     * 假设nums数组的长度是n，下标从0开始到n-1
     * 我们用f(i)代表以第i个数结尾的 连续子数组的最大和 ，那么很显然我们要求的答案就是：
     * max 0<=i<=n-1 {f(i)}
     * 因此我们只需要求出每个位置的f(i)，然后返回f数值中的最大值即可。那么我们如何求f(i)呢？我们可以考虑nums[i]
     * 单独成为一段还是加入f(i-1)对应的那一段，这取决于nums[i]和f(i-1)+nums[i]的大小，我们希望获得一个比较大的，
     * 于是可以写出这样的动态规划转移方程：f(i)=max{f(i-1)+num[i],nums[i]}
     * 不难给出一个时间复杂度O(n)、空间复杂度O(n)的实现，即用一个f数组来保存f(i)的值，用一个循环求出所有f(i).考虑
     * 到f(i)只和f(i-1)相关，于是我们可以只用一个变量pre来维护对于当前f(i)的f(i-1)的值是多少，从而让空间复杂度降低
     * 到O(1)，这有点类似 滚动数组 的思想
     **/
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    /**
     * 分治
     * 我们定义一个操作get(a,l,r)表示查询a序列[l,r]区间内的最大子段和，那么最终我们要求的答案就是get(nums,0,nums.size()-1).
     * 如何分治实现这个操作呢？对于一个区间[l,r]，我们取m=(l+r)/2，对区间[l,m]和[m+1,r]分治求解,当递归逐层深入直到区间长度缩小
     * 为1的时候，递归 开始回升 。这个时候我们考虑如何通过[l,m]区间的信息和[m+1,r]区间的信息合并区间[l,r]的信息。最关键的两个问题是：
     * 我们要维护区间的哪些信息呢？ 我们如何合并这些信息呢？
     * 对于一个区间[l,r]，我们可以维护四个量：
     * lsum表示[l,r]内以l为左端点的最大子段和
     * rsum表示[l,r]内以r为右端点的最大子段和
     * msum表示[l,r]内最大字段和
     * isum表示[l,r]的区间和
     * 以下简称[l,m]为[l,r]的 左子区间 [m+1,r]为[l,r]的 右子区间 。我们考虑如何维护这些量呢(如何通过左右子区间的信息合并得到[l,r]
     * 的信息)？对于长度为1的区间[i,i]，四个量的值都和nums[i]相等。对于长度大于1的区间：
     * 1、首先最好维护的是isum，区间[l,r]的isum就等于 左子区间 的isum加上 右子区间的isum
     * 2、对于[l,r]的lsum，存在两种可能，它要么等于 左子区间 的lsum，要么等于 左子区间 的isum加上 右子区间 的lsum，二者取大。
     * 3、对于[l,r]的rsum，同理，它要么等于 右子区间 的rsum，要么等于 右子区间 的isum加上 左子区间 的rsum，二者取大。
     * 4、当计算好上面的三个量之后，就很好计算[l,r]的msum了，我们可以考虑[l,r]的msum对于的区间是否跨越m—它可能不跨越m，也就是说[l,r]
     * 的msum可能是 左子区间 的msum和 右子区间 的msum中的一个，它也可能跨越m，可能是 左子区间 的rsum和 右子区间 的lsum求和。三个取大。
     **/
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray1(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}
